
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2153. -- 设计铁路 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2153: 设计铁路</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>259 MB<br><span class=green>Submit: </span>41&nbsp;&nbsp;<span class=green>Solved: </span>20<br>[<a href='submitpage.php?id=2153'>Submit</a>][<a href='problemstatus.php?id=2153'>Status</a>][<a href='bbs.php?id=2153'>Discuss</a>]</center><h2>Description</h2><div class=content><p>A省有一条东西向的公路经常堵车，为解决这一问题，省政府对此展开了调查。调查后得知，这条公路两侧有很多村落，每个村落里都住着很多个信仰c教的教徒，每周日都会开着自家的车沿公路到B地去&ldquo;膜拜&rdquo;他们的教主，这便是堵车的原因。详细调查显示：这里总共有N个村落，并且它们都在B地的东边。编号为i的村落住有Ri个信仰c教的教徒，距离B地的距离为Ti（单位：公里）。为解决这一问题，A省政府决定在这条公路下修建一条地下快速铁路来缓解交通，并沿线修建若干个车站（B地会修建终点站，不算车站）。每名教徒都会先往B地方向开车（如果他所在村庄处恰好有车站就不必开车了），到最近的一个快速铁路车站时换乘（如果直接开到B地就不用换乘了），再通过快速铁路到B地。但A政府遇到一个难题：修建多少个车站以及在哪修建车站。一个修建车站的方案中，如果修建过多的车站则会花费过多的钱，但修建的车站少了或者修建的位置不对又会导致公路的拥堵。A政府为了协调这两方面，采用评分的方式来衡量一个方案的好坏（分数越大方案越坏）：每修建一个车站会增加m的分数，在某一次&ldquo;膜拜&rdquo;中（只考虑去，不考虑返回），每导致1个教徒开车行驶1公里会增加1分。现请你设计一个修建车站的方案，使得分数最小。请输出这个最小的分数。</p></div><h2>Input</h2><div class=content><p>输入的第一行包含两个正整数n、m。之后n行每行两个正整数Ti、Ri。</p></div><h2>Output</h2><div class=content><p>输出一个整数，表示最小的分数。</p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>【样例输入1】<br />
4 20<br />
25 3<br />
5 3<br />
25 2<br />
20 5<br />
【样例输入2】<br />
4 30<br />
25 3<br />
5 3<br />
25 2<br />
20 5<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
【样例输出1】<br />
55<br />
<br />
【样例输出2】<br />
70<br />
【样例说明】<br />
样例1中，在距B地20km处和距B地25km处修建车站，1、3、4号村落里的教徒就不必开车了，得分20*2=40分。2号村落里的教徒直接开车到B地，得分3*5=15分。总共得分55分。<br />
样例2中，在距B地20km处修建车站，4号村落里的教徒就不必开车了，得分30分。1号和3号村落里的教徒先开车到距B地20km处的车站，得分3*5+2*5=25分。2号村落里的教徒直接开车到B地，得分3*5=15分。总共得分70分。<br />
【数据规模】<br />
对于100%的数据，n<=40000，m<=2000000000，Ti<=1000000，Ri<=1000。<br />
提示：请注意使用64位整型存储某些数据和结果。<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=By 钱桥'>By 钱桥</a></p></div><center>[<a href='submitpage.php?id=2153'>Submit</a>][<a href='problemstatus.php?id=2153'>Status</a>][<a href='bbs.php?id=2153'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
